Rod Cutting

Statement#

You are given a rod of length n meters. You can cut the rod into smaller pieces, and each piece has a price based on its length. Your task is to earn the maximum revenue that can be obtained by cutting up the rod into smaller pieces.

Let’s say you have a rod of length $4$ meters and you have two lists: one that defines the lengths, and the other that defines the price of each length.

lengths = [1, 3, 4]

prices = [2, 7, 8]

You can cut the rod into the pieces of varying lengths and earn the following revenues:

• Four pieces of length $1$ meter $= 2 + 2 + 2 + 2 = 8$

• One piece of length $1$ meter and another piece of length $3$ meters $= 2 + 7 = 9$

• One single piece of length $4$ meters $= 8$

Therefore, the maximum revenue you can generate by cutting the rod and selling the pieces is $9$, by cutting the rod into two pieces, one of length $1$ and the other of length $3$.

Constraints:

• $1\leq$ n $\leq900$
• $1\leq$ prices[i] $\leq10^6$
• $1\leq$ lengths[i] $\leq n$
• prices.length $=$ lengths.length

Examples#

Try it yourself#

Implement your solution in the following playground.

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution#

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Unbounded Knapsack dynamic programming pattern.

Naive approach#

The idea of this algorithm is to exhaustively find the most optimal pieces of the rod from all the possible combinations. We do this by making recursive calls with all possible values of length and choosing those that give us the highest revenue.

For example, we have a rod of length $n = 3$ meters. Given below is the length of each piece with its price:

• lengths: $[1, 2, 3]$
• prices: $[3, 7, 8]$

Let’s look at all the possible combinations to find those pieces of a rod which yield the maximum revenue:

• $1, 1, 1$ => $(3 + 3 + 3)$ $= 9$
• $1, 2$ => $(3 + 7)$ $= 10$
• $3$ => $8$

The calculation above shows that we need a recursive solution to find all possible combinations. We make recursive calls for each piece length and calculate the revenue for all possible pieces to find the maximum among them.

The visualization below shows a dry run of this algorithm.

We will divide our problem into smaller subproblems, starting from the start of the lengths list and for each length, we will do the following steps:

• If the remaining rod length is zero or if we have traversed all of our lengths, we return 0. This represents the base case where no further cutting is possible.

• Otherwise, perform the following two steps:

  • If we can cut a piece of length lengths[curr], where curr specifies the index of the piece length we are considering from the lengths array, we’ll add its price into our earned revenue and recursively evaluate the maximum earnings from the remaining rod. Else, if we cannot cut a piece of length lengths[curr], we’ll simply move to the next step.

  • Evaluate the maximum earning without cutting a piece of current length from the rod.

  • Return the maximum earnings earned from both of the steps.

Let’s implement the algorithm as discussed above:

Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.

Time complexity#

At every step, we can have at most two possibilities. Either we can make a cut, or we can leave it as it is. Therefore, for a rod of length $n$, the time complexity of the naive approach is $O(2^{n})$.

Space complexity#

As the maximum depth of the recursive call tree is $n$ and each call stores its data on the stack, the space complexity of this approach is $O(n)$.

Optimized solution using dynamic programming#

As the recursive solution to this problem is very costly, let’s see if we can reduce this cost. Dynamic programming helps us to avoid recomputing the same subproblems. Now let’s analyze our recursive solution to see if it has the properties needed for conversion to dynamic programming.

• Optimal substructure: The optimal substructure property applies to this problem because if we make an optimal cut at some point, then the resulting subproblems will also be optimal. For example, suppose we have a rod of length $8$ and the prices for different lengths are as follows:

  lengths: [1, 2, 3, 4, 5, 6, 7, 8]

  prices: [1, 5, 8, 9, 10, 17, 17, 20]

  If we make an optimal cut at position $4$, then the left subproblem (the rod of length $4$) will also be optimal, and the same is true for the right subproblem (the rod of length $4$). This is because any suboptimal cut in either subproblem will lead to a lower overall profit, so the optimal solution must be based on the optimal solutions of both subproblems.

• Overlapping subproblems: The overlapping subproblems property applies to this problem because there are multiple subproblems that are solved multiple times. For example, when solving the rod cutting problem for a rod of length $8$, the subproblem of finding the maximum profit for a rod of length $4$ will be solved multiple times, when trying to solve the left subproblem for the cut at position $4$ and when trying to solve the right subproblem for the cut at position $4$.

Now that we have seen the properties, we can build the solution using dynamic programming.

Top-down solution#

The top-down solution, commonly known as the memoization technique, is an enhancement of the recursive solution. It overcomes the problem of calculating redundant solutions over and over again by storing them.

The recursive tree calculates the results of many subproblems multiple times. Therefore, if we store the result of each subproblem in a table, we can improve the algorithm’s efficiency by accessing the required value at a constant time. This reduces the number of recursive calls we need to evaluate our results.

Therefore, we need a 2-D table of size len(lengths) $\times$ n + 1 to store the maximum revenue earned for each rod of length $n$ into a pieces of given lengths. We start our solution by creating a table dp and initializing it with -1 and a helper function that assists us in calculating the maximum revenue earned. If you look at the code below, you’ll see that the helper function has the following steps:

• If the remaining rod length is zero or if we have traversed all of our lengths, we return 0.

• If we haven’t already computed a revenue for a given rod length $n$ and a current length at lengths[curr], we compute it as we did in the naive approach and store the result at dp[curr][n]. Here, curr specifies the index of the piece length we are considering from the lengths array.

• Otherwise, we return the already computed result from the table by fetching it from dp[curr][n].

The value at dp[curr][n] represents the maximum earning that can be obtained by cutting a rod of length $n$ into pieces of length lengths[curr]. For example, if we have a rod of length $3$ and we are allowed to cut pieces of size $2$ from it. A single piece of size $2$ has a price $7$. The maximum revenue earned will be $7$ by cutting the rod into 1 piece of size $2$. A rod of length $1$ will be left, which can not be cut further, therefore, will not be included in the revenue.

Let’s implement the above discussed algorithm below:

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

The time complexity for the algorithm above is $O(n \times k)$, where $n$ is the total length of the rod, and $k$ is len(lengths).

Space complexity#

The space complexity for this algorithm is $O(n \times k)$. This is because we have created a table of size $k \times n$, where $k$ is len(lengths), and $n$ is the total length of the rod.

Bottom-up solution#

The bottom-up solution, also known as the tabulation method, is an iterative method of solving dynamic programming problems. Like other typical dynamic programming problems, recomputations of the same subproblems can be avoided by constructing a table dp to store the intermediate results.

Essentially, we want to find the maximum revenue earned for every rod length and for every given piece lengths. The idea is to start building from the rod of length 1 and then use the result to solve the problems of bigger lengths.

Therefore, for every possible piece size at index curr, where 0 <= curr <= lengths, we need to compute the maximum earning for all rod lengths, rod_length, from $1$ to $n$. If you look at the code below, you’ll see two loops where we do the following steps at each iteration:

• Consider the piece of length lengths[curr]. If we can get it from the rod of length rod_length, we add its revenue to the revenue we earned from the remaining rod length as:

revenue1 = prices[curr] + dp[curr][rod_length - lengths[curr]]

• Do not consider the piece and take the revenue we earned for the same rod length but by considering the pieces of the previous length as:

revenue2 = dp[curr - 1][rod_length]

• Take the maximum from both of the revenues earned and store it as:

dp[curr][rod_length] = max(revenue1, revenue2)

After performing all the calculations, we have the result at the last cell of our table.

Look at the following illustration for an understanding of this algorithm. The illustration below is for the rod of length $3$.

Note: At any iteration, if there are two blue cells, that means we are considering all the three steps as mentioned above. Otherwise, we are only taking a single step from the steps mentioned above.

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

The time complexity for the algorithm above is $O(n \times k)$, where $n$ is the total length of the rod, and $k$ is len(lengths).

Space complexity#

The space complexity for this algorithm is $O(n \times k)$. This is because we have created a table of size $k \times n$, where $k$ is len(lengths), and $n$ is the total length of the rod.